Curso de ScriptVox Intermedirio - Aula 13 - Prof. Oswaldo Vernet - iNCE/UFRJ

Vamos examinar mais atentamente, nesta aula, o percurso em listas.

Em primeiro lugar, precisamos entender o que significa exatamente percorrer uma lista.
Um PERCURSO em uma lista consiste em executar uma certa ao sobre cada um dos elementos, 
na ordem em que eles aparecem na lista.

A primeira ideia que surge para implementar um percurso  caminhar pelos elementos da lista
um por um, executando a ao desejada. Podemos, portanto, utilizar uma varivel inteira
que, comeando em 0, v assumindo sucessivamente os valores 0, 1, 2, e assim por diante.
Cada valor assumido pela varivel corresponder a uma posio da lista e, portanto,
a varivel ser usada para INDEXAR a lista. Porm, o valor desta varivel no deve crescer
indefinidamente:  preciso parar quando alcanamos a ltima posio. Das aulas anteriores, 
j sabemos que a ltima posio tem por ndice o nmero de elementos da lista (ou seja, 
sua cardinalidade) menos um, j que o primeiro elemento  o da posio zero.

Se utilizarmos o comaando REPETE, devemos ter um cuidado: a varivel de controle deste
comando varia de um at o limite especificado. Entretanto, a lista comea na posico
zero e no na posio um. Mas isto  simples de contornar:  s usar como ndice o
valor da varivel de controle menos um.

Assim, imaginando que a varivel "texto" armazene uma lista cujos elementos so cadeias,
gostaramos de escrever na tela cada uma dessas cadeias. O comando REPETE poderia ser usado
da seguinte forma:

repete i TAMANHO(texto)
	escreve texto[i-1]          // Usa o valor de "i" menos um para indexar a lista
fim repete

A varivel de controle do comando REPETE  a varivel "i", que assumir os valores
1, 2, etc... at TAMANHO(texto). Lembre que a funo TAMANHO, aplicada a uma lista,
retorna o nmero de elementos da lista. Porm, na hora de utilizar a varivel como
ndice da lista, subtramos um, para comear da posio 0 e ir at a ltima posio
da lista.

Neste caso, a ao executada  simplesmente escrever o elemento. Mas poderia ser
qualquer outra, to complexa quanto se queira.

Voc j se perguntou como a funo POS  implementada?  Esta funo, quando aplicada
a listas, espera dois parmetros: um dado a ser procurado e uma lista. Ela retorna
a posio do dado na lista, caso ele corresponda a algum elemento da lista, ou 
menos um, caso o dado no aparea em nenhuma posio.

Vamos mostrar como esta funo poderia ser implementada. Para no haver conflito 
com a funo POS nativa, vamos cham-la de PROCURA. Segue-se o cdigo:

* incio da funo PROCURA
funo PROCURA (dado, lista) : i
	se TIPO(lista) <> "lista" retorna -1
	repete i TAMANHO(lista)
		se dado = lista[i-1] retorna i-1
	fim repete
	retorna -1
fim funo
* fim da funo PROCURA

A funo PROCURA recebe dois parmetros: o "dado" a ser procurado e a "lista" na qual
se dar a procura. A varivel "i"  local  funo.

O primeiro teste  apenas por cautela: usamos a funo TIPO para conferir se
realmente o segundo parmetro armazena uma lista. Esta funo retorna uma cadeia
informando o tipo do que  passado como parmetro para ela. 

Em seguida, o comando REPETE  usado, tendo "i" como varivel de controle.
Esta varivel "i" vai assumir sucessivamente os valores 1, 2, e assim por diante,
at o limite TAMANHO(lista). Para indexar a lista, devemos usar o valor de "i"
menos um.

A ao propriamente dita consiste apenas em perguntar se o contedo da varivel
"dado"  igual ao contedo da posio "i" menos um da lista. Se for igual,  porque o
dado se encontra nesta posio; neste caso, retornamos a posio em que ele foi
encontrado.

Observe o ltimo comando da funo: 

retorna -1

Este comando s ser executado se todas as comparaes forem falsas, ou seja,
se o "dado" no estiver em nenhuma posio da lista. Por isto, retornamos menos
um, j que este valor no corresponde a nenhuma posiao vlida.

Uma pergunta: j que uma lista pode conter elementos repetidos, o que acontece
se o dado aparecer em mais de uma posio da lista?  Da maneira como foi programada, 
a funo PROCURA s informar a posio correspondente  primeira ocorrncia do dado.

Para que a funo PROCURA nos informe todas as ocorrncias, devemos mudar o tipo
de retorno que ela fornece: em vez de uma posio, a funo passaria a retornar uma
lista de posies, informando todas as ocorrncias de "dado" em "lista". Se "dado"
no for encontrado em "lista", podemos retornar a lista vazia. As alteraes
ficariam assim:

* incio da funo PROCURA
funo PROCURA (dado, lista) : posies, i
	posies := []
	se TIPO(lista) <> "lista" retorna posies
	repete i TAMANHO(lista)
		se dado = lista[i-1] posies[] := i - 1
	fim repete
	retorna posies
fim funo
* fim da funo PROCURA

A varivel local "posies" armazenar uma lista de todas as posies em
que "dado" ocorrer na lista. Portanto, antes de comearmos o percurso, ela 
inicializada com a lista vazia.

Se o tipo do segundo parmetro no for lista, a funo retorna o valor da
varivel "posies", que, neste momento,  a lista vazia. 

Durante o percurso, quando o teste 

dado = lista[i-1]

for verdadeiro, isto significa que "dado" foi encontrado na posio "i" menos um; 
portanto, esta posio  anexada  lista de posies. Se, terminado o percurso,
o dado nunca for encontrado, a varivel "posies" permanecer em seu estado
inicial, armazenando a lista vazia durante todo o percurso.

Acabado o percurso, a lista armazenada em "posies"  retornada.

Como esta nova verso da funo PROCURA deve ser chamada no script?
Considere o exemplo a seguir:

* incio do exemplo de como usar a nova funo PROCURA
L := [2, 3, 4, 2, 4, 6, 8, 0, 4, 6]

escreve "Dado a buscar: " &
l dado
enquanto dado <> ""
	p := PROCURA (dado, L)
	escreve p
	escreve "Dado a buscar: " &
	l dado
fim enquanto
* fim do exemplo de como usar a nova funo PROCURA

A lista "L"  inicializada com alguns elementos inteiros. Se digitarmos o
valor "4" como dado a buscar, dever aparecer na tela a seguinte linha:

[2, 4, 8]

que  exatamente a lista das posies em que "dado" ocorre em "L". 
Se for necessrio ter acesso a essas posies, basta armazenarmos a lista 
retornada pela funo PROCURA em alguma varivel e, depois, percorr-la.
Segue-se o cdigo:

* incio do exemplo
onde := PROCURA (dado, L)

para p em onde
	escreve "A informao " dado " ocorre na posio " p " da lista L"
fim para
* fim do exemplo

Neste ltimo exemplo, utilizamos outra forma de percorrer uma lista: 
atravs do comando PARA, j introduzido em aulas anteriores. Qual a diferena 
entre as duas maneiras de percorrer uma lista?

Quando usamos o comando REPETE, estamos percorrendo a lista atravs de suas
posies, comeando em zero e avanando at a cardinalidade da lista menos um.
 atravs do valor da varivel de controle menos um que temos acesso aos 
elementos, usando a INDEXAO.

Quando usamos o comando PARA, temos acesso direto aos elementos da lista na
ordem em que eles aparecem, sem precisar INDEXAR a lista. A varivel de controle 
do comando PARA denomina-se um ITERADOR e ela assume sucessivamente os valores de
cada um dos elementos da lista.

Ento, como decidir qual comando usar?   simples: se apenas os elementos da
lista nos interessam, devemos usar o comando PARA; porm, se, alm dos elementos,
as posies tambm nos interessam, devemos usar o comando REPETE, tomando o valor
da varivel de controle menos um como ndice para a lista. 

No exemplo anterior, as posies  que so importantes; por isso, o comando REPETE
foi o escolhido.


EXERCCIOS

Exerccio de avaliao (enviar para scriptvox@gmail.com at o meio-dia de 5 de maro de 2012)

Faa um script que l, de um arquivo, os nomes e as notas dos alunos de
uma turma. Para evitar decimais, considere as notas de 0 a 100. Os nomes 
e notas devem ser guardados em uma nica lista de alunos, sendo cada aluno, 
 uma varivel compartimentada, consistindo de dois compartimentos: o nome e a nota.

Ao final, o script dever informar a mdia da turma (no se importe com decimais)
e os nomes e notas dos alunos superiores ou iguais  mdia.     

Bom estudo! 

Oswaldo Vernet
